#include <iostream>
using namespace std;

void BubbleSort1(int arr[], int num) {
  int i, j;
  for (i = 0; i < num; i++) {
    for (j = 1; j < num - i; j++) {
      if (arr[j - 1] > arr[j]) std::swap(arr[j - 1], arr[j]);
    }
  }
}
// 改进思路：设置标志位，明显如果有一趟没有发生交换（flag = flase)，说明排序已经完成.
void BubbleSort2(int arr[], int num) {
  int k = num;
  int j;
  bool flag = true;
  while (flag) {
    flag = false;
    for (j = 1; j < k; j++) {
      if (arr[j - 1] > arr[j]) {
        std::swap(arr[j - 1], arr[j]);
        flag = true;
      }
    }
    k--;
  }
}
void selection_sort(int arr[], int num) {
  for (int i = 0; i < num - 1; i++) {
    int min = i;
    for (int j = i + 1; j < num; j++)
      if (arr[j] < arr[min]) min = j;
    std::swap(arr[i], arr[min]);
  }
}

void insertion_sort(int arr[], int len) {
  for (int i = 1; i < len; i++) {
    int key = arr[i];
    int j = i - 1;
    while ((j >= 0) && (key < arr[j])) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
}

int main(int argc, char** argv) {
  const int N = 20;
  int a1[N], a2[N], a3[N];
  for (int i = 0; i < N; i++) {
    a1[i] = rand() % 100;  // 生成100以内随机数
    a2[i] = a1[i];
    a3[i] = a1[i];
  }
  cout << "origin: ";
  for (int i = 0; i < N; i++) cout << a1[i] << " ";
  cout << endl;

  BubbleSort1(a1, N);
  cout << "BubbleSort: ";
  for (int i = 0; i < N; i++) cout << a1[i] << " ";
  cout << endl;

  selection_sort(a2, N);
  cout << "SelectSort: ";
  for (int i = 0; i < N; i++) cout << a2[i] << " ";
  cout << endl;

  insertion_sort(a3, N);
  cout << "InsertSort: ";
  for (int i = 0; i < N; i++) cout << a3[i] << " ";
  cout << endl;
  auto a = 1;

  return 0;
}